package battleGame;

import java.util.*;


public class AStarSearch {
World myWorld;

public AStarSearch(World w){
	
	myWorld = w;
}


  public static class PriorityList extends LinkedList {

    public void add(Comparable object) {
      for (int i=0; i<size(); i++) {
        if (object.compareTo(get(i)) <= 0) {
          add(i, object);
          return;
        }
      }
      addLast(object);
    }
  }


  /**
    Construct the path, not including the start node.
  */
  protected List constructPath(AStarNode node) {
    LinkedList path = new LinkedList();
    while (node.pathParent != null) {
      path.addFirst(node);
      node = node.pathParent;
    }
    return path;
  }

  public List getNeighbors(AStarNode node){
	  
	  List<AStarNode> neighbors = new ArrayList<AStarNode>();
	  //get upper neighbor
	  
	 int index = node.id-myWorld.numCols;
	 AStarNode neighbor;
	 if(index>=0)//valid upper limit
	 {
		neighbor= getNodeFromID(index);
		if(neighbor.isEmpty)
			neighbors.add(neighbor);
		//else
			//System.out.println("Node "+neighbor.id+ " is NOT empty");
	 }
	 index = node.id+myWorld.numCols;
	 if(index<myWorld.numCols*myWorld.numRows)//valid lower limit
	 {
		neighbor= getNodeFromID(index);
		if(neighbor.isEmpty)
			neighbors.add(neighbor);
		//else
			//System.out.println("Node "+neighbor.id+ " is NOT empty");
	 }
	 
	 index = node.id; //check left
	 //get rows and cols of node
	 
	 if(index%myWorld.numCols!=0)//check left corner
	 {
		 index--;
		neighbor= getNodeFromID(index);
		if(neighbor.isEmpty)
			neighbors.add(neighbor);
		//else
			// System.out.println("Node "+neighbor.id+ " is NOT empty");
		
	 }
	 index = node.id; //check right
	 index++;
	 if(index%myWorld.numCols!=0)//check left corner
	 {
		 
		neighbor= getNodeFromID(index);
		if(neighbor.isEmpty)
			neighbors.add(neighbor);
		//else
			//System.out.println("Node "+neighbor.id+ " is NOT empty");
		
	 }
	  return neighbors;
	  
  }
  
  public AStarNode getNodeFromID(int id)
  {
	  Tile tile = new Tile(-1,"ERROR",false);
	  for(int i = 0; i<myWorld.numRows;i++){
		  
		  for(int j=0; j<myWorld.numCols;j++)
		  {
			  if(myWorld.GetTile( j, i ).id==id)
				  tile = myWorld.GetTile( j, i );
		  }
	  }
	  return tile;
	  
  }

  /**
    A list
    of AStarNodes is returned, or null if the path is not
    found. 
  */
  public List findPath(AStarNode startNode, AStarNode goalNode) {

    PriorityList openList = new PriorityList();
    LinkedList closedList = new LinkedList();

    startNode.costFromStart = 0;
    startNode.estimatedCostToGoal =
      startNode.getEstimatedCost(goalNode);
    startNode.pathParent = null;
    openList.add(startNode);

    while (!openList.isEmpty()) {
      AStarNode node = (AStarNode)openList.removeFirst();
      if (node == goalNode) {
        // construct the path from start to goal
        return constructPath(goalNode);
      }

      List neighbors = getNeighbors(node);
      for (int i=0; i<neighbors.size(); i++) {
        AStarNode neighborNode =
          (AStarNode)neighbors.get(i);
        boolean isOpen = openList.contains(neighborNode);
        boolean isClosed =
          closedList.contains(neighborNode);
        double costFromStart = node.costFromStart +
          node.getCost(neighborNode);

        // check if the neighbor node has not been
        // traversed or if a shorter path to this
        // neighbor node is found.
        if ((!isOpen && !isClosed) ||
          costFromStart < neighborNode.costFromStart)
        {
          neighborNode.pathParent = node;
          neighborNode.costFromStart = costFromStart;
          neighborNode.estimatedCostToGoal =
            neighborNode.getEstimatedCost(goalNode);
          if (isClosed) {
            closedList.remove(neighborNode);
          }
          if (!isOpen) {
            openList.add(neighborNode);
          }
        }
      }
      closedList.add(node);
    }

    System.out.println("no path found");
    return null;
  }
  
    static public List<AStarNode> performSearch( int colOrigin, int rowOrigin, int colDest, int rowDest )
	{
    	World world = World.GetInstance();
    	if( world == null )
    		return null;
		AStarSearch mySearch = new AStarSearch( world );
		List<AStarNode> path;
		
//		System.out.print( "Buscando de " + colOrigin + ", " + rowOrigin + " hacia " + colDest + ", " + rowDest + "  - ");
		Tile start = world.GetTile( colOrigin, rowOrigin );
		Tile goal = world.GetTile( colDest, rowDest );
		if( start == null || goal == null )
			return null;
//		System.out.print( "Desde el tile " + start.id + " hasta el tile " + goal.id + "  -  " );
		path = mySearch.findPath(start, goal);
		return path; //return the first occurence of the list
	}

}